package 字符串;

/**
 * @author ssh
 * @date 2025/9/1
 * @description 给你一个字符串 s ，请你反转字符串中 单词 的顺序。
 *
 * 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
 * 输入：s = "the sky is blue"
 * 输出："blue is sky the"
 */
public class 翻转字符串中的单词 {
    public String reverseWords(String s) {
        // System.out.println("ReverseWords.reverseWords2() called with: s = [" + s + "]");
        // 1.去除首尾以及中间多余空格
        StringBuilder sb = removeSpace(s);
        // 2.反转整个字符串
        reverseString(sb, 0, sb.length() - 1);
        // 3.反转各个单词
        reverseEachWord(sb);
        return sb.toString();
    }




    private StringBuilder removeSpace(String s) {
        int left = 0, right = s.length() - 1;
        // 跳过开头空格
        while (left <= right && s.charAt(left) == ' ') left++;
        // 跳过结尾空格
        while (left <= right && s.charAt(right) == ' ') right--;
        StringBuilder sb = new StringBuilder();
        while (left <= right) {
            char c = s.charAt(left);
            if (c != ' ') {
                sb.append(c);
            } else if (sb.length() > 0 && sb.charAt(sb.length() - 1) != ' ') {
                // 只保留一个空格
                sb.append(' ');
            }
            left++;
        }
        return sb;
    }

    private void reverseString(StringBuilder sb, int i, int j) {
        while (i<j){
            char temp= sb.charAt(i);
            sb.setCharAt(i,sb.charAt(j));
            sb.setCharAt(j,temp);
            i++;
            j--;
        }
    }
    private void reverseEachWord(StringBuilder sb) {
        int start = 0;
        int end = 0;
        int n = sb.length();

        while (start < n) {
            // 找到单词的结束位置
            while (end < n && sb.charAt(end) != ' ') {
                end++;
            }
            // 反转当前单词
            reverseString(sb, start, end - 1);
            // 移动到下一个单词的开始
            start = end + 1;
            end = start;
        }

    }

    public static void main(String[] args) {
        // 测试代码
        String s = "  the sky   is blue  ";
        翻转字符串中的单词 solution = new 翻转字符串中的单词();
        String result = solution.reverseWords(s);
        System.out.println(result); // 输出: "blue is sky the"
    }
}
